2018 “百度之星”程序设计大赛 - 初赛（A）

imily's notebook

2018-08-12

比赛

http://bestcoder.hdu.edu.cn/contests/contest_show.php?cid=825

AC一道。。。rank1959。。。又参加了有趣的B场，还是很值得一记的！

A. 度度熊拼三角

题意略。

三角形，两边之和大于第三边，两边之差小于第三边。

那么我们把边的长度排序，枚举最小的两条边 l, r, 找到最大的一条小于两边之和的边。用 two-pointers.

code:

#include <bits/stdc++.h>
using namespace std;

int n, a[1005], ans;

int main() {
    while (~scanf("%d", &n)) {
        for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
        sort(a + 1, a + n + 1);
        ans = -1;
        int r;
        for (int j = 2; j < n; j++) {
            r = j + 1;
            for (int i = 1; i < j; i++) {
                while (r < n && a[i] + a[j] > a[r + 1]) ++r;
                if (a[i] + a[j] > a[r])
                    ans = max(ans, a[i] + a[j] + a[r]);
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

B. 度度熊学队列

题意略。

可以用STL中的map模拟双向链表。

code:

#include <bits/stdc++.h>
using namespace std;

int n, Q, flag, u, v, w, val;

map<int, deque<int> >a;

void read(int &x){
	char ch = getchar();x = 0;
	for (; ch < '0' || ch > '9'; ch = getchar());
	for (; ch >='0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
}

int main() {
    while (cin >> n >> Q) {
        a.clear();
        while (Q--) {
            read(flag);
            if (flag == 1) {
                read(u), read(w), read(val);
                if (w == 0) a[u].push_front(val);
                else a[u].push_back(val);
            } else if (flag == 2) {
                read(u), read(w);
                if (!a[u].empty()) {
                    if (w == 0) {
                        cout << a[u].front() << endl;
                        a[u].pop_front();
                    } else {
                        cout << a[u].back() << endl;
                        a[u].pop_back();
                    }
                } else cout << -1 << endl;
            } else {
                read(u), read(v), read(w);
                if (w == 0) {
                    a[u].insert(a[u].end(), a[v].begin(), a[v].end());
                    a[v].clear();
                } else {
                    a[u].insert(a[u].end(), a[v].rbegin(), a[v].rend());
                    a[v].clear();
                }
            }
        }
    }
    return 0;
}

C. 度度熊剪纸条

题意略。

官方题解很有道理！对于每一段连续的1，如果左边右边都有数字，那就是二元组 [1, 1]，含义是左边切一刀、右边切一刀；如果只有左边有数字，那就是 [1, 0], 反之是 [0, 1]，或者是 [0, 0]。

现在，我们要在这些集合里挑选一些段，使得中括号里代价和不超过 K，排序后从大到小选，O(N log N).

code:

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
int n, k, cnt, cnt1, ans, b[4];
char s[N];

struct node {int d, w;}kk[N];

int cmp(node a, node b) {return a.d == b.d ? a.w < b.w : a.d > b.d;}

void work(int k, int tmp) {
    for (int i = 1; i <= cnt; i++)
        if (k >= kk[i].w) {
            tmp += kk[i].d, k -= kk[i].w;
        }
    ans = max(ans, tmp);
}

int main() {
    while (~scanf("%d%d", &n, &k)) {
        scanf("%s", s + 1);
        if (k == 0) {
            ans = 0;
            for (int i = 1; i <= n; i++) {
                if (s[i] == '1') ans++;
                else break;
            }
            printf("%d\n", ans);
            continue;
        }
        int num = 0;
        cnt = cnt1 = 0;
        for (int i = 1; i <= n; i++) {
            if (s[i] == '1') {
                num++;
                if (i == n) b[++cnt1] = num;
            } else if (num) {
                if (i - 1 == num) b[++cnt1] = num;
                else kk[++cnt].d = num, kk[cnt].w = 2;
                num = 0;
            }
        }
        k++;
        ans = 0;
        sort(kk + 1, kk + 1 + cnt, cmp);
        if (cnt1 == 2) {
            work(k, 0), work(k - 1, b[1]), work(k - 1, b[2]), work(k - 2, b[1] + b[2]);
        } else if (cnt1 == 1) {
            work(k, 0), work(k - 1, b[1]);
        } else work(k, 0);
        printf("%d\n", ans);
    }
    return 0;
}

D. 度度熊看球赛

题意略。

这是一个伪的概率。(2N)! 指的是情况数，每种情况对ans的贡献是 $D^K$，其中 k 表示该情况下有 K 对情侣座位相邻。

设 $F_{i, j}$ 表示共有 i 对情侣，且正好有 j 对是挨着坐的。每次考虑把第 i + 1 对放进去：

(1). 这对情侣合在一起放。

① 拆散一对情侣：$F_{i + 1, j} += F_{i, j} * j$

② 放在情侣之间的空隙间：$F_{i + 1, j + 1} += F_{i, j} (2 i + 1 - j)$

(2). 这对情侣分开放。

① 他们各自拆散了一对情侣：$F_{i + 1, j - 2} += F_{i, j} (j \frac{(j - 1)}{2})$

② 只有一个人拆散了一对情侣：$F_{i + 1, j - 1} += F_{i, j} (2 i + 1 - j)$

③ 没有情侣被拆散：$F_{i + 1, j} += F_{i, j} ((2 i + 1 - j) \frac{2 i - j}{2})$

$O(N^2)$ 预处理。对于每一组询问，我们只要 O(N) 扫一遍计算一下答案即可。

code:

#include <bits/stdc++.h>
using namespace std;

const int mod = 998244353, N = 1010;
typedef long long ll;
ll f[N][N], n, d;

ll quick_pow(ll a, ll b) {
    ll ret = 1;
    for (; b; b >>= 1) {
        if (b & 1) ret = ret * a % mod;
        a = a * a % mod;
    } return ret;
}

int C(ll a, ll b = 2) {
    return a * (a - 1) % mod * quick_pow(b, mod - 2) % mod;
}

void ycl() {
    f[1][1] = 2;
    int cnt = 0;
    for (int i = 1; i <= 1000; i++) {
        f[i + 1][0] = 2 * f[i][0] % mod * C(2 * i + 1, 2) % mod +
                      2 * f[i][1] % mod * 2 * i % mod + 
                      2 * f[i][2] % mod;
        f[i + 1][0] %= mod;
        for (int j = 1; j <= i + 1; j++) {
            f[i + 1][j] = 2 * f[i][j - 1] % mod * (2 * i + 1 - (j - 1)) % mod +
                          2 * f[i][j] % mod * (j + C(2 * i + 1 - j, 2)) % mod +
                          2 * f[i][j + 1] % mod * ((j + 1) * (2 * i + 1 - (j + 1)) % mod) % mod +
                          2 * f[i][j + 2] % mod * C(j + 2, 2) % mod;
            f[i + 1][j] %= mod;
        }
    }
    return;
}

int main() {
    ycl();
    while (~scanf("%lld%lld", &n, &d)) {
        ll ans = 0;
        if (n == 1) {
            printf("%lld\n", 2 * d % mod);
            continue;
        }
        for (int i = 0; i <= n; i++) {
            ans = (ans + f[n][i] * quick_pow(d, i) % mod) % mod;
        }
        printf("%lld\n", ans);
    }
    return 0;
}